#include "FordFulkerson.h"


class Bricks
{
public:
    bool run(const string& word, const vector<string>& bricks);
    string getBricks() const;
private:
    void constructGraph(const string& word, const vector<string>& bricks);
    vector<vector<int>> graph;
    vector<bool> path;
    int bricksNumber;
    string result;
};

void Bricks::constructGraph(const string& word, const vector<string>& bricks)
{
    bricksNumber = bricks.size();
    // матрица графа:
    // вершины - буквы слова и кубики
    // плюс источник и сток - первый и последний столбцы
    graph.resize(word.size() + bricksNumber + 2);

	for (int i = 0; i < graph.size(); ++i)
    {
		graph[i].resize(graph.size());
	}

	for (int j = 1; j <= bricksNumber; ++j)
	{
	    // проводим ребра от источника к каждому из кубиков
		graph[0][j] = 1;
		for (int i = 0; i < word.size(); ++i)
		{
			for (int k = 0; k < bricks[j-1].size(); ++k)
			{
			    // из каждого кубика проводим ребро в букву входного слова,
			    // если эта буква на нем есть
				if (bricks[j - 1][k] == word[i])
				{
					graph[j][bricksNumber + 1 + i] = 1;
				}
			}
		}
	}

    // от всех букв слова
    // проводим ребра в сток
	for (size_t i = 0; i < word.size(); ++i)
	{
		graph[bricksNumber + 1 + i][graph.size() - 1] = 1;
	}
}


bool Bricks::run(const string& word, const vector<string>& bricks)
{
    constructGraph(word, bricks);

    // в path храним информацию, через какие кубики пройдет поток
	path.resize(graph.size());

    // eсли идет поток мощности равной длине слова -
    // он проходит по достаточному для составления слова числу кубиков
	if (FordFulkerson::run(graph, 0, graph.size() - 1, path, bricksNumber, result) >= word.size())
    {
        return true;
	}
	else
	{
		return false;
	}
}

string Bricks::getBricks() const
{
    return result;
}
